/* 链表 */
typedef struct _Node
{
    void *data;
    struct _Node *prev;
    struct _Node *next;
} Node;
typedef Node List;

void InitList(List *list)
{
    list->prev = list;
    list->next = list;
}

void AddBack(List *list, void *data)
{
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = data;

    p->next = list;
    p->prev = list->prev;
    list->prev->next = p;
    list->prev = p;
}

void RemoveNode(Node *p)
{
    p->next->prev = p->prev;
    p->prev->next = p->next;
    free(p->data);
    free(p);
}

int IsEmptyList(List *list)
{
    return list == list->next && list == list->prev;
}

int GetListSize(List *list)
{
    int n = 0;
    for (Node *p = list->next; p != list; p = p->next) {
        n++;
    }
    return n;
}

void ShowList(List *list)
{
    printf("Size:%d Data:", GetListSize(list));
    printf("[HEAD]");
    for (Node *p = list->next; p != list; p = p->next) {
        printf(" %s", p->data);
    }
    printf(" [TAIL]\n");
}

void RemoveList(List *list)
{
    while (!IsEmptyList(list)) {
        RemoveNode(list->prev);
    }
}

void next(char *str, int left, int right, int n, List *list)
{
    if (left + right >= 2 * n) {
        void *data = malloc(strlen(str) + 1);
        strcpy(data, str);
        AddBack(list, data);
        return;
    }

    if (left < n) {
        strcat(str, "(");
        next(str, left + 1, right, n, list);
        str[left + right] = '\0';
    }

    if (left > right) {
        strcat(str, ")");
        next(str, left, right + 1, n, list);
        str[left + right] = '\0';
    }
}

char ** generateParenthesis(int n, int* returnSize)
{
    List list;
    InitList(&list);

    char *str = malloc(2 * n + 1);
    *str = 0;
    next(str, 0, 0, n, &list);
    // ShowList(&list);

    int size = GetListSize(&list);
    char **result = (char **)malloc(size * sizeof(char *));
    int i = 0;
    for (Node *p = list.next; p != &list; p = p->next) {
        result[i] = (char *)malloc(n * 2 + 1);
        strcpy(result[i], p->data);
        i++;
    }
    RemoveList(&list);
    free(str);

    *returnSize = size;
    return result;
}